package com.zxy.leetcode._00000_00099._00030_00039;

/**
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
 *
 * 搜索旋转排序数组
 * 升序排列的整数数组 nums 在预先未知的某个点上进行了旋转
 * （例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
 *
 * 请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
 *
 * 思路：二分查找
 */
public class Test00033 {

    public static void main(String[] args) {
        Test00033 test = new Test00033();
        int[] nums = {4,5,6,7,0,1,2};
        System.out.println(test.search(nums, 0));
        System.out.println(test.search(nums, 3));
        System.out.println(test.search(nums, 4));

        int[] nums2 = {1, 2, 3, 4, 5, 6};
        System.out.println(test.search(nums2, 4));
    }

    public int search(int[] nums, int target) {
        if (nums.length <= 3) {
            for (int i=0; i<nums.length; i++) {
                if(nums[i] == target) {
                    return i;
                }
            }
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        // 尝试分割为两个数组，两个都是升序的，分割点是mid
        while (left < right) {
            mid = (left + right)/2;
            if (nums[mid] < nums[left]) {
                right = mid;
            }else if (nums[mid] > nums[right]) {
                left = mid;
            }else {
                // 说明不需要分割两个数组了
                return search(nums, 0, nums.length-1, target);
            }

            if (right - left == 1) {
                // 最小nums[mid] 最大nums[mid-1]
                mid = right;
                break;
            }
        }

        left = 0;
        right = nums.length - 1;
        if (nums[mid] > target) {
            return -1;
        }
        if (nums[mid-1] < target) {
            return -1;
        }
        // 判断是要走哪一部分数组
        if (nums[0] <= target) {
            right = mid-1;
        }else {
            left = mid;
        }

        return search(nums, left, right, target);
    }

    private int search(int[] nums, int left, int right, int target) {
        int mid = -1;
        while (left <= right) {
            mid = (left + right)/2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                right = mid-1;
            }else {
                left = mid+1;
            }
        }
        return -1;
    }

    /*
    官方解法，一次循环，
    每次从有序的部分进行匹配
     */
    public int search2(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }

}
